package com.hy.doubleCompete.Two127;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:
 * User:Mr.Du
 * Date:2024/3/30
 * Time:23:57
 */
public class SumOfPowers {

    public int sumOfPowers(int[] nums, int k) {
        int MOD = 1000000007;
        int n = nums.length;
        int[][] dp = new int[n][k + 1];

        for (int i = 0; i < n; i++) {
            dp[i][1] = 0;
        }

        for (int j = 2; j <= k; j++) {
            for (int i = j - 1; i < n; i++) {
                int minEnergy = Integer.MAX_VALUE;
                for (int prev = j - 2; prev < i; prev++) {
                    minEnergy = Math.min(minEnergy, dp[prev][j - 1]);
                }
                dp[i][j] = (minEnergy + Math.abs(nums[i] - nums[i - 1])) % MOD;
            }
        }

        int res = 0;
        for (int i = k - 1; i < n; i++) {
            res = (res + dp[i][k]) % MOD;
        }

        return res;
    }
}
